#include <iostream>
using namespace std;

// 二分查找元素索引
int binary_search(int nums[], int target, int n) {
    int left = 0;
    int right = n;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) 
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else right = mid;
    }
    return -1;
}

// 二分查找符合条件元素的左边界
int left_bound(int nums[], int target, int n) {
    if (n < 0) return -1;
    int left = 0;
    int right = n;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            right = mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else right = mid;
    }
    if (left == n) return -1;
    return nums[left] == target ? left : -1;
}

// 二分查找符合条件元素的右边界
int right_bound(int nums[], int target, int n) {
    if (n < 0) return -1;
    int left = 0;
    int right = n;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            left = mid + 1;
        else if (nums[mid] < target) 
            left = mid + 1;
        else right = mid;
    }
    if (right == 0) return -1;
    return nums[right - 1] == target ? (right - 1) : -1;
}